package leetcode;

import java.util.Arrays;

public class NextGreatElement {

	public static void main(String[] args) {
		int[] array = {3, 6, 10, 11, 15, 16, 19};
		NextGreatElement object = new NextGreatElement();
//		System.out.println(object.binarySearch(array, 0, array.length - 1, 14));
		int n = 14;
		System.out.println(object.nextGreaterElement(n));
	}
	
	public int nextGreaterElement(int n) {
        int[] digits = new int[32];
        int length = 0;
        while(n != 0){
        	digits[length++] = n % 10;
        	n /= 10;
        }
        if(length == 1){
        	return -1;
        }
        //首先如果该数字是逆序的，比如98752那么肯定没有比它大的，直接返回-1
        //由于我们是从0为开始存储的，所以检查是否是小于
        boolean canFind = false;
        int firstIndex = 0;
        for(int i = 1; i < length; i++){
        	if(digits[i] < digits[i - 1]){
        		canFind = true;
        		firstIndex = i;
        		break;
        	}
        }
        if(!canFind){
        	return -1;
        }
        //策略：首先找到最右边的顺序对
        //如果该顺序对满足 3 6 5 ...这种形式，那么最小的应该是5 然后按照数字递增的顺序排列...
        //如果是3 6 2 1...这样的那就是6 然后按照数字递增的顺序排列
        //总之就是先对0 ... firstIndex排序，然后选择最小的大于digits[firstIndex]的
        int temp = digits[firstIndex];
//        Arrays.sort(digits, 0, firstIndex + 1);
//        for(int i = 0; i < firstIndex; i++){
//        	if(digits[i] > temp){
//        		
//        	}
//        }
        //不用排序，因为我们找到了第一个逆序对，说明肯定是有序的
        //比如 1 2 4 5 2
        int firstMoreThan = binarySearch(digits, 0, firstIndex - 1, temp);
        swap(digits, firstMoreThan, firstIndex);
        
        //此时的数组为1 2 2 5 4,最小的应该是 5 2 2 1 4
        //为了避免交换，我们自己处理这个逻辑
        long res = 0;
        for(int i = length - 1; i >= firstIndex; i--){
        	res = res * 10 + digits[i];
        }
        for(int i = 0; i < firstIndex; i++){
        	res = res * 10 + digits[i];
        }
        return res > Integer.MAX_VALUE ? -1 : (int)res;
	}
	
	//找到大于target的第一个下标
	public int binarySearch(int[] array, int left, int end, int target){
		if(left > end){
			return -1;
		}
		if(array[end] < target){
			return -1;
		}
		int middle;
		while(left < end){
			middle = (end + left) / 2;
			if(array[middle] > target){
				end = middle;
			}else{
				left = middle + 1;
			}
		}
		return left;
	}
	
	public void swap(int[] array, int i, int j){
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}
